package org.example.myleet.p461;

/**
 * 0 ms
 * 位运算计算汉明距离，先做一次异或得到x和y的不同位为1的结果z
 * 然后逐位检查是0或1，方法是右移再左移，使末尾位变成0，然后与原数做一次异或如果结果结果==1就可以知道末尾位是1
 */
public class Solution {
    public int hammingDistance(int x, int y) {
        int z = x ^ y, count = 0;
        while (z > 0) {
            int a = z >> 1 << 1;
            if ((z ^ a) == 1) {
                ++count;
            }
            z = a >> 1;
        }
        return count;
    }

    /**
     * 一行解决版本，底层使用分治的方式每16、8、4、2位做一次与运算得到1的数量
     */
//    public int hammingDistance(int x, int y) {
//        return Integer.bitCount(x ^ y);
//    }

    /**
     * Brian Kernighan 算法
     * f(x) = x & (x−1)
     */
//    public int hammingDistance(int x, int y) {
//        int s = x ^ y, ret = 0;
//        while (s != 0) {
//            s &= s - 1;
//            ret++;
//        }
//        return ret;
//    }
}
